/**
 * 称呼定义： 
 *  1. 插入调整中
 *   子节点： 双红节点中下面的红色节点
 *   父节点： 双红节点中上面面的红色节点（“子节点的父节点”）
 *   祖父节点： “父节点”的父节点
 *  
 *  2. 删除调整中
 *   子节点： 双重黑节点
 *   兄弟节点： 双重黑节点的兄弟节点
 *   父节点： 双重黑节点的父节点
 * 
 * 颜色定义： 值可以表示： 黑颜色的数量
 *  0： 红 节点
 *  1： 黑 节点
 *  2： 双重黑 节点
 * 
 *    黑节点 = 红节点 + 1；
 *    双重黑 = 黑节点 + 1；
 *    红节点 = 黑节点 - 1；
 *    黑节点 = 双重黑 - 1；
 */

const NIL = {
  key = undefined,
  color = 0,
  lChild = null,
  rChild = null,
}
// 0：红   1：黑   2：双重黑
class Node {
  constructor(key, color = 0, lChild = NIL, rChild = NIL) {
    this.key = key;
    this.color = color;
    this.lChild = lChild;
    this.rChild = rChild;
  }
}

function getNewNode(key) {
  return new Node(key);
}

// 是否含有红色子节点
function has_red_child(root) {
  return root.lChild.color === 0 || root.rChild.color === 0;
}
function left_roate(root) {
  let newRoot = root.rChild;
  root.rChild = newRoot.lChild;
  newRoot.lChild = root;
  return newRoot;
}
function right_roate(root) {
  let newRoot = root.lChild;
  root.lChild = newRoot.rChild;
  newRoot.rChild = root;
  return newRoot;
}
function getPre(root) {
  let temp = root.lChild;
  while(temp.rChild !== NIL) temp = temp.rChild;
  return temp;
}

// 在root上插入值为key的节点， 并返回新root
Node.prototype.insert = function(root, key) {
  root = this._insert(root, key);
  // 插入操作结束后，强行将根节点改为黑色。ß
  root.color = 1;
  return root;
}
Node.prototype._insert = function(root, key) {
  if(root === NIL) return getNewNode(key);
  if(key === root.key) return root;
  if(key < root.key) {
    root.left = this._insert(root.left, key);
  } else {
    root.right = this._insert(root.right, key);
  }
  return insert_maintrain(root); // 干掉红红
}
/**
 * 插入操作后，干掉红红的情况。返回调节后的新root
 * 插入操作站在祖父节点向下看。 *root为祖父节点*
 */
 Node.prototype.insert_maintrain = function(root) {
  // 判断是否失衡，分别检测root和左右子节点是否存在红红。
  let flag = 0;  // 0: 没有红红的情况   1：L失衡（红红情况在祖父节点左侧）   2：R失衡（红红情况在祖父节点右侧）
  if(root.lChild.color === 0 && has_red_child(root.lChild)) flag = 1; // L
  if(root.rChild.color === 0 && has_red_child(root.rChild)) flag = 2; // R
  if(flag === 0) return root;
  /**
   * 情况一: 父节点为红色，叔节为红色
   * 
   * 调整策略： 
   *  父节点和叔节点变为黑色， 祖父节点变为红色
   */
  if(root.lChild.color === 0 && root.rChild.color === 0) {
    root.color = 0; // 祖父改为红色
    root.lChild.color = root.rChild.color = 1; // 父 和 叔改为黑色
    return root;
  }

  /**
   * 情况二：父节点为红色，叔节点为黑色
   *  根据父节点和子节点位置分为： LL、LR、RR、RL
   * 
   * 调整策略： 
   *  1. 旋转（ 同AVL ）
   *  2. 红色上浮 或者 红色下沉
   */

  // 1. 旋转操作
  if(flag === 1) { // 红色父节点在祖父节点左侧 - L
    if(root.lChild.rChild.color === 0) { // 红色子节点在父节点右侧 - LR
      root.lChild = left_roate(root.lChild);
    }
    root = right_roate(root); // 
  } else { // - R
    if(root.rChild.lChild === 0) { // - RL
      root.rChild = right_roate(root.rChild);
    }
    root = left_roate(root);
  }
  // 2. 红色上浮
  root.color = 0;
  root.lChild.color = root.rChild.color = 1;
  return root;
}

// 在root上删除值为key的节点，平衡调节， 并返回新root。
Node.erase = function(root, key) {
  root = this._erase(root, key);
  root.color = 1;
  return root;
}
Node.prototype._erase = function(root, key) {
  if(root === NIL) return root;
  if(key < root.key) {
    root.left = this._erase(root.left, key);
  } else if(key > root.key) {
    root.right = this._erase(root.right, key);
  } else {
    if(root.rChild === NIL || root.rChild === NIL) { // 删除度为0 和 1的节点。 
      let temp = root.lChild === NIL ? root.rChild : root.lChild; // 0：返回NIL, 1: 返回子节点
      /** important 
       * 删除调整：下面一行代码兼容的删除调整的四种情况。
       *  删除的节点为：
       *   度1红: 不存在这样节点。
       *   度0红: 无黑颜色，不影响操作。
       *   度1黑: 子只能为红，黑颜色给子节点。
       *   度0黑: 将黑颜色给NIL，产生了双重黑节点。
       */
      temp.color += root.color;

      delete root;
      return temp;
    } else { // 删除度为2的节点， 通过前驱节点转换为度为0或1的问题。
      let temp = getPre(root);
      root.key = temp.key;
      root.lChild = this._erase(root.lChild, temp.key);
    }
  }
  
  return erase_maintain(root); // 干掉双重黑
}
/**
 * 删除操作后，干掉双重黑节点。返回调节后的新root。
 * 删除操作站在父节点向下看。 *root为父节点*
 */
Node.prototype.erase_maintain = function(root) {
  if(root.lChild.color !== 2 && root.rChild.color !== 2) return root; // 没有双重黑
  /**
   * 情况四： 双重黑的兄弟节点为 红色
   * 
   * 调整策略： 
   *  1. 根据红色的兄弟节点位置，进行旋转。（在左侧：右旋； 在右侧：左旋）
   *  2. 老root变为红色，新root变为黑色。（新老root交换颜色）
   *  3. 转变为了双重黑节点的兄弟节点为 黑色的情况
   */
  if(has_red_child(root)) {
    let flag = 0; // 记录红色节点在哪侧。 1: 红色在左侧  2: 红色在右侧
    root.color = 0; // 2. 老root节点变为红色
    if(root.lChild.color === 0) { // 1. 旋转
      root = right_roate(root);
      flag = 1;
    } else {
      root = left_roate(root);
      flag = 2;
    }
    root.color = 1; // 3. 新root节点变为黑色
    
    if(flag = 1) { // 4. 转变为了双重黑节点的兄弟节点为黑色的情况。 
      root.rChild = this.erase_maintain(root.rChild); // 双重黑在右侧
    } else {
      root.lChild = this.erase_maintain(root.lChild); // 双重黑在左侧
    }
    return root;
  }

  /**
   * 双重黑的兄弟节点为黑色
   *  情况一：兄弟节点为黑色 且 兄弟节点的子节点都为黑色
   * 
   *  调整策略：
   *    1. 双重黑和兄弟节点都减一层黑色
   *    2. 父节点加一层黑色
   */
  if(
    root.lChild.color === 1 && !has_red_child(root.lChild) || // 黑色兄弟节点在左侧，且兄弟节点没有红色子节点
    root.rChild.color === 1 && !has_red_child(root.rChild)    // 黑色兄弟节点在右侧，且兄弟节点没有红色子节点
  ) {
    root.lChild.color -= 1;
    root.rChild.color -= 1;
    root.color += 1;
    return root;
  }
  /**
   * 双重黑的兄弟节点为黑色
   *  兄弟节点为黑色 且 兄弟节点的子节点有红色
   *    根据 兄弟节点 位置和 兄弟的红孩子的位置 分为： LL、LR、RR、RL
   * 
   *    情况二：兄弟节点的位置和其红色子节点的位置在同侧。- LL RR
   *    调整策略：
   *      1. 旋转
   *      2. 新根节点变为老根节点颜色
   *      3. 新根节点的两个子节点（旋转后的子节点）变为黑色
   *      4. 双重黑调为正常黑
   *    情况三：兄弟节点的位置和其红色子节点的位置在异侧。- LR RL
   *      1. 先小旋
   *      2. 新根节点变为黑色 
   *      3. 老根节变为红色
   *      4. 转为情况二
   */
  if(root.lChild.color === 1) { // 黑色兄弟在左侧 - L。（则双重黑在右侧）

    root.rChild.color = 1; // 4. 双重黑变为正常黑
    //（ 判断右侧为红 转为 判断左侧不为红。 因为左右都为红按LL处理 ）
    if(root.lChild.lChild.color != 0) { // 兄弟节点右侧子节点为红色：情况三: LR
      root.lChild.color = 0; // 老根节点变为红
      root.lChild = left_roate(root.lChild);
      root.lChild.color = 1; // 新根节点变为黑
    }
    //       新根节点     老根节点
    root.lChild.color = root.color; // 2. 新根节点颜色改为老根节点颜色
    root = right_roate(root);
  } else { // 黑色兄弟在右侧 - R。
    root.lChild.color = 1;
    if(root.rChild.rChild.color != 0) { // 情况三: RL
      root.rChild.color = 0;
      root.rChild = right_roate(root.rChild);
      root.rChild.color = 1;
    }
    root.rChild.color = root.color;
    root = left_roate(root);
  } 
 
  root.lChild.color = root.rChild.color = 1; // 3. 新根节点的两个子节点变为黑色
  return root;
}